#include <stdio.h>
#include <stdlib.h>

typedef struct TREENODE TreeNode;
typedef int ElementType;

struct TREENODE {
	ElementType elm;
	TreeNode *left;
	TreeNode *right;
	int lh;
	int rh;
	int bf;
};

int calcHigh(TreeNode *);
TreeNode* addNode(TreeNode*,ElementType);
void preOrder(TreeNode*);

int main(void){
	TreeNode *root=NULL;
	root=addNode(root,30);
	root=addNode(root,20);
	root=addNode(root,40);
	root=addNode(root,50);
	root=addNode(root,10);
	root=addNode(root,15);
	//root=addNode(root,35);
	preOrder(root);
	return 0;
}

int calcHigh(TreeNode *root){
	if( !root )
		return 0;
	root->lh=calcHigh(root->left)+1;
	root->rh=calcHigh(root->right)+1;
	root->bf=root->lh - root->rh ;
	return root->lh > root->rh ? root->lh : root->rh;
}

TreeNode* addNode(TreeNode* root,ElementType elm){
	TreeNode *head=root;
	TreeNode **target=&head;
	while( root ){
		if( elm > root->elm ){
			target=&(root->right);
			root=root->right;
		}else{
			target=&(root->left);
			root=root->left;
		}
	}
	TreeNode *new=malloc(sizeof(TreeNode));
	new->elm=elm;
	new->left=new->right=NULL;
	new->lh=new->rh=new->bf=0;
	*(target)=new;
	calcHigh(head);
	return head;
}

void preOrder(TreeNode *root){
	if( NULL == root )
		return;
	printf("V:%d H:%d BF:%d\n",root->elm,(root->lh > root->rh ? root->lh:root->rh),root->bf);
	preOrder(root->left);
	preOrder(root->right);
	return;
}
